\documentclass[12pt]{exam}

\usepackage{amsmath}
\usepackage{verbatim}
%\usepackage{graphicx}
\usepackage{gastex}
\usepackage{timestamp} % http://brasserie-seul.com/?Recipes&nr=16

\addpoints

\renewcommand{\solutiontitle}{\noindent\textbf{Solution:}\par\noindent}

\begin{document}

\printanswers

\pagestyle{head}
\firstpageheader{CS 59000-05}{Exam}{Fall 2014}

% just in case we need an image file
%\includegraphics[width=2in]{problem.png}

The following questions ask you to analyze some code fragments and to write some code fragments. When you analyze some code, your analysis should be written in complete sentences organized into paragraphs. Do not write sentence fragments and do not write the most terse answer that you can think of (even if it is essentially correct). You are being graded on your ability to communicate, not just on your ability to arrive at correct solutions.

\bigskip

When you write code fragments, you do not need to write compilable code. Just make sure that your code is not in any way ambiguous.

\bigskip

Write all your answers neatly using a computer document format. You can write your answers in a plain text file, a MS Word document, an HTML page, or even in \LaTeX. Put your exam, and any supporting files that you might like to submit (like compilable code), in a zip file and submit your zip file to me using Blackboard.

\bigskip

Each person should work on this exam by them self. If you have any questions about the exam, feel free to send me an e-mail.

\bigskip

This exam should be turned in by Friday, December 19.

\vspace*{\fill}
\newpage

\begin{questions}


\question
The following code outlines a synchronization pattern. Assume that the two threads begin at the same time, each thread runs on its own core, and there are no other (significant) threads running on the cores.

\vspace{-.15truein}
\begin{verbatim}
void *thread1(void *vargp)
{  while(1)
   {  << do Calculation A >>
      sem_post(&semaphore1);
      << do Calculation B >>
      sem_post(&semaphore2);
      sem_wait(&semaphore3);
   }
}

void *thread2(void *vargp)
{  while(1)
   {  sem_wait(&semaphore1);
      << do Calculation C >>
      sem_post(&semaphore3);
      sem_wait(&semaphore2);
   }
}

sem_t semaphore1, semaphore2, semaphore3;

int main()
{  pthread_t tid;
   sem_init(&semaphore1, 0, 0); // not signaled
   sem_init(&semaphore2, 0, 0); // not signaled
   sem_init(&semaphore3, 0, 0); // not signaled
   pthread_create(&tid, NULL, thread1, NULL);
   pthread_create(&tid, NULL, thread2, NULL);
   while(1){ Sleep(1000); }
}
\end{verbatim}

\begin{parts}

\part[15]
In what way are the two threads synchronized? Give your answer in terms of how the three calculations, A, B, and C, are ordered in time. Explain carefully what role each of the three semaphores plays in the synchronization.

\begin{solution}
   % put your solution to problem 1a here
\end{solution}

\vspace*{\fill}

\part[15]
Rewrite this program using condition variables.

\begin{solution}
   % put your solution to problem 1b here
\end{solution}

\end{parts}



\vspace*{\fill}
\newpage


\question
Suppose that we have five C functions
\begin{comment}
\begin{verbatim}
   void functionA(void);
   void functionB(void);
   void functionC(void);
   void functionD(void);
   void functionE(void);
\end{verbatim}
\end{comment}
that together solve some problem. Suppose these functions, labeled {\tt A} through {\tt E}, depend on each other according to the following graph.

\smallskip
\unitlength=1cm
\begin{picture}(5,2.6)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,2){$A$}
\node(B)(6,2){$B$}
\node(C)(8,2){$C$}
\node(D)(7,1){$D$}
\node(E)(5,0){$E$}
% transitions
\drawedge(A,E){}
\drawedge(B,D){}
\drawedge(C,D){}
\drawedge(D,E){}
\end{picture}

\smallskip
Each edge of the graph denotes a dependency between two of these functions. For example, the edge from node B to node D means that {\tt functionB} must be called, and must return, before {\tt functionD} can be called.

\begin{parts}
\part[10]
What is wrong with this sketch of a C program that uses Pthreads to execute the five functions in parallel in a way that adheres to the above dependency graph? How would you improve this program (but still use five worker threads and only the Pthreads functions {\tt pthread\_create()} and {\tt pthread\_join()})?
\begin{verbatim}
void *threadA(void *vargp){ functionA(); }
void *threadB(void *vargp){ functionB(); }
void *threadC(void *vargp){ functionC(); }
void *threadD(void *vargp){ functionD(); }
void *threadE(void *vargp){ functionE(); }
int main()
{  pthread_t tidA, tidB, tidC, tidD, tidE;
   pthread_create(&tidB, NULL, threadB, NULL);
   pthread_create(&tidC, NULL, threadC, NULL);
   pthread_join(tidB, NULL);
   pthread_join(tidC, NULL);
   pthread_create(&tidA, NULL, threadA, NULL);
   pthread_create(&tidD, NULL, threadD, NULL);
   pthread_join(tidA, NULL);
   pthread_join(tidD, NULL);
   pthread_create(&tidE, NULL, threadE, NULL);
   pthread_join(tidE, NULL);
}
\end{verbatim}

\begin{solution}
   % put your solution to problem 2a here
\end{solution}


\vspace*{\fill}
\newpage


\part[10]
Write another sketch of a Pthreads program to execute the above five functions in a way that is maximally parallel (i.e., always runs as many threads in parallel as possible), adheres to the above dependency graph, and uses the minimal number of threads possible (including the {\tt main()} thread). Your solution should still use only {\tt pthread\_join()} for synchronization.

\begin{solution}
   % put your solution to problem 2b here
\end{solution}

%\vspace*{\fill}

\part[10]
Write a sketch of a Java program that uses Fork-Join to execute the above five functions in a way that adheres to the above dependency graph, is maximally parallel, and uses the minimum number of threads.

Assume that the five functions are static methods in a class called {\tt MyTasks.java}. Write a sketch of a {\tt main()} method and whatever classes that you need that extend {\tt java.util.concurrent.RecursiveAction}.

\begin{solution}
   % put your solution to problem 2c here
\end{solution}

\end{parts}

%\vspace*{\fill}

\question[15]
Suppose that we have six C functions
\begin{verbatim}
   void functionA(void);   void functionD(void);
   void functionB(void);   void functionE(void);
   void functionC(void);   void functionF(void);
\end{verbatim}
that together solve some problem. Suppose these function depend on each other according to the following dependency graph.

%\smallskip
\unitlength=1cm
\begin{picture}(5,3.5)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,3){$A$}
\node(B)(6,3){$B$}
\node(C)(8,3){$C$}
\node(D)(7,2){$D$}
\node(F)(4.5,1.5){$F$}
\node(E)(5,0){$E$}
% transitions
\drawedge(A,F){}
\drawedge(B,D){}
\drawedge(B,F){}
\drawedge(C,D){}
\drawedge(D,E){}
\drawedge(F,E){}
\end{picture}

\smallskip
Write a sketch of a C program that uses Pthreads to execute the above six functions in a way that is maximally parallel, but adheres to the above dependency graph. Give a written explanation of how your code solves the problem. You can use any synchronization mechanism you want (join, condition variables, semeaphores, etc.).

\begin{solution}
   % put your solution to problem 3 here
\end{solution}



\vspace*{\fill}
\newpage


\question
Suppose we wanted to implement our own mutex class in Java.
\begin{verbatim}
   class MyMutex {
      public Thread locked = null;

      public void lock() throws InterruptedException {
         if ( this.locked != null )
            this.wait();
         this.locked = Thread.currentThread();
      }

      public void unlock() {
         if ( this.locked == Thread.currentThread() ) {
            this.notify();
            this.locked = null;
         } else
            throw new IllegalStateException();
      }
   }
\end{verbatim}

\begin{parts}
\part[10]
Correct the mistakes in this impelentation of a mutex class. Explain the reason for each of your corrections. In particular, what could go wrong if each particular correction isn't made? (You can ignore the {\tt throws InterruptedException}. It is needed for the code to compile.)

\begin{solution}
   % put your solution to problem 4a here
\end{solution}

\vspace*{\fill}

\part[5]
The documentation for {\tt pthread.h}
\begin{verbatim}
 http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mutex_lock.html
\end{verbatim}
says that the pthread library implements several kinds of mutexes, {\tt PTHREAD\_MUTEX\_NORMAL}, {\tt PTHREAD\_MUTEX\_ERRORCHECK}, {\tt PTHREAD\_MUTEX\_RECURSIVE}, and {\tt PTHREAD\_MUTEX\_DEFAULT}. Use the Java documentation
\begin{verbatim}
https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html
\end{verbatim}
to determine which of these kinds of pthread mutexes our repaired Java mutex is most similar to with respect to the {\tt lock()} method. Explain why.

\begin{solution}
   % put your solution to problem 4b here
\end{solution}

\vspace*{\fill}

\part[5]
With respect to the {\tt unlock()} method, which of the above kinds of pthread mutexes is our repaired Java mutex most similar to? Explain why.

\begin{solution}
   % put your solution to problem 4c here
\end{solution}


\vspace*{\fill}
\newpage


\part[5]
The proper way to use one of our MyMutex objects looks like this.
\begin{verbatim}
   mutex.lock();
   // do something
   mutex.unlock();
\end{verbatim}

Explain carefully what would happen, and why, if you used one of our corrected MyMutex objects like this.
\begin{verbatim}
   mutex.lock();
   // do something
   mutex.notify();
\end{verbatim}

\begin{solution}
   % put your solution to problem 4d here
\end{solution}

\end{parts}



\vspace*{\fill}

%Total of \numpoints\ points

\hfill\timestamp  % add a time stamp at lower right hand corner

\end{questions}

\end{document}